package com.yoshino.leetcode.oneHundred.twentyninth;

import java.util.Arrays;

class Solution {
    public boolean isMatch2(String s, String p) {
        return s.matches(p);
    }

    public boolean isMatch(String s, String p) {
        int n = s.length() + 1;
        int m = p.length() + 1;
        boolean[][] dp = new boolean[n][m];
        // 两个都是空
        dp[0][0] = true;


        for (int i = 0; i < n ; i++) {
            for (int j = 0; j < m; j++) {
                // 分成空正则匹配和非空正则
                if (j == 0) {
                    dp[i][j] = i == 0;
                } else {
                    // 非空分为两个情况 * 和 非*
                    if (p.charAt(j - 1) != '*') {
                        if (i > 0 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')) {
                            dp[i][j] = dp[i - 1][j - 1];
                        }
                    } else {
                        // 碰到 *，分为要和不要两种情况
                        // 不要
                        if (j >= 2) {
                            dp[i][j] = dp[i][j - 2];
                        }
                        if (i >= 1 && j >= 2 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')) {
                            dp[i][j] |= dp[i - 1][j];
                        }
                    }
                }
            }
        }
        return dp[n - 1][m - 1];
    }

    public int nthUglyNumber(int n) {
        // 丑数 可以由 另一个丑数 * 2 / 3 / 5 来获得
        if (n < 1) {
            return -1;
        }
        int dp[] = new int[n];
        dp[0] = 1;
        int id2 = 0, id3 = 0, id5 = 0;
        for (int i = 1; i < n; i++) {
            dp[i] = Math.min(dp[id2] * 2, Math.min(dp[id3] * 3, dp[id5] * 5));
            if (dp[i] == dp[id2] * 2) {
                id2++;
            }
            if (dp[i] == dp[id3] * 3) {
                id3++;
            }
            if (dp[i] == dp[id5] * 5) {
                id5++;
            }
        }
        return dp[n - 1];
    }

    public double[] dicesProbability(int n) {
        // 状态方程：f(n, x) = f(n - 1, x - i) 求和(i = 1...6) * 1 / 6
        double[] dp = new double[6];
        Arrays.fill(dp, 1.0 / 6);
        // 骰子个数
        for (int i = 2; i <= n; i++) {
            // 对于 n 个骰子取数范围是 1 * i ~ 6 * i
            // 实际意义第一个数是 n
            double[] cur = new double[5 * i + 1];
            // 遍历上一次的全部值，每个值都可以加 1 ~ 6 的数值（多一个骰子）
            for (int j = 0; j < dp.length; j++) {
                // 状态方程：f(n, x) = f(n - 1, x - i) 求和(i = 1...6) * 1 / 6
                for (int k = 0; k < 6; k++) {
                    cur[j + k] += dp[j] * (1.0 / 6);
                }
            }
            dp = cur;
        }
        return dp;
    }

}